#include <vector>

using namespace std;

// sum in [1, i]
class BIT
{
    vector<int> arr;
    int N;

public:
    BIT(int n) : N(n), arr(n + 1) {}
    static constexpr int lowbit(int i)
    {
        return i & -i;
    }
    void update(int index, int val)
    {
        while (index <= N)
        {
            arr[index] += val;
            index += lowbit(index);
        }
    }
    int getsum(int index) const
    {
        int result = 0;
        while (index > 0)
        {
            result += arr[index];
            index -= lowbit(index);
        }
        return result;
    }
};